class HashTable<T = any> {
  private storage: [string, T][][] = [];
  private length: number = 7; // 哈希表长度
  private count: number = 0; // 当前存放的元素个数
  private limit: number = 0.75; // 装填因子
  private minLimit: number = 0.25; // 最小装填因子

  // 质数函数
  private isPrime(num: number): boolean {
    const sqrt = Math.sqrt(num);
    for (let i = 2; i <= sqrt; i++) {
      if (num % i === 0) {
        return false;
      }
    }
    return true;
  }

  private getNextPrime(num: number): number {
    while (!this.isPrime(num)) {
      num++;
    }
    return num;
  }

  // 哈希表扩容/缩容函数
  private resize(newLength: number) {
    let newPrime = this.getNextPrime(newLength);
    if (newLength < this.length) newPrime = 7;
    this.length = newPrime;

    let oldStorage: [string, T][][] = this.storage;
    this.storage = [];
    this.count = 0;
    oldStorage.forEach((bucket) => {
      if (!bucket) return;
      bucket.forEach(([key, value]) => {
        this.put(key, value);
      });
    });
  }

  // 哈希函数
  /**
   *
   * @param key 哈希表的键
   * @param max 哈希表的最大长度
   * @returns
   */
  private hashFunc(key: string, max: number): number {
    let hashCode = 0;
    let len = key.length;
    for (let i = 0; i < len; i++) {
      hashCode = 31 * hashCode + key.charCodeAt(i);
      console.log(hashCode, key.charCodeAt(i));
    }

    const index = hashCode % max;
    // console.log(hashCode, index, max);

    return index;
  }

  // 哈希表插入/更新函数
  put(key: string, value: T) {
    const index = this.hashFunc(key, this.length);
    let bucket = this.storage[index];
    if (!bucket) {
      bucket = [];
      this.storage[index] = bucket;
    }

    let isUpdate = false;
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      const tupleKey = tuple[0];
      if (tupleKey === key) {
        tuple[1] = value;
        isUpdate = true;
      }
    }

    if (!isUpdate) {
      bucket.push([key, value]); // 插入数据
      this.count++;
      const loadFactor = this.count / this.length;
      // 如果负载因子超过0.75，则进行扩容
      if (loadFactor > this.limit) {
        this.resize(this.length * 2);
      }
    }
  }

  // 哈希表删除函数
  delete(key: string): T | undefined {
    const index = this.hashFunc(key, this.length);
    const bucket = this.storage[index];

    if (!bucket) return undefined;

    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      const tupleKey = tuple[0];
      if (tupleKey === key) {
        bucket.splice(i, 1);
        this.count--;
        // if (!bucket.length) {
        //   delete this.storage[index];
        // }

        const loadFactor = this.count / this.length;
        // 当哈希表项数小于 1/4 时，将数组长度resize成原来的一半
        if (loadFactor < 0.25 && this.length > this.minLimit) {
          this.resize(Math.floor(this.length / 2));
        }
        return tuple[1]; // 返回删除的值
      }
    }

    return undefined; // 没找到返回undefined
  }

  // 哈希表获取函数
  get(key: string): T | undefined {
    const index = this.hashFunc(key, this.length);
    const bucket = this.storage[index];

    if (!bucket) return undefined;

    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      const tupleKey = tuple[0];
      const tupleValue = tuple[1];
      if (tupleKey === key) {
        return tupleValue;
      }
    }
    return undefined;
  }

  // 哈希表的数据结构
  get getSelection(): [string, T][][] {
    return this.storage;
  }
}

const hashTable = new HashTable();
hashTable.put("name", "张三");
hashTable.put("age", 18);
hashTable.put("gender", "男");
hashTable.put("list", "李四");
hashTable.put("aaa", 19);
hashTable.put("ccc", 999);
console.log(hashTable.getSelection);

console.log(hashTable.get("name")); // 张三
console.log(hashTable.get("age")); // 18
console.log(hashTable.get("gender")); // 男
// hashTable.delete("aaa");
hashTable.delete("ccc");
// hashTable.delete("list");
console.log(hashTable.getSelection);

export default HashTable;
